翻訳と辞書
Words near each other
・ Well-being
・ Well-bird exam
・ Well-covered graph
・ Well-defined
・ Well-Deserved Obscurity
・ Well-Done (album)
・ Well-field system
・ WELL-FM
・ Well-formed
・ Well-formed document
・ Well-formed element
・ Well-formed formula
・ Well-formed Petri net
・ Well-Founded Fear
・ Well-founded phenomenon
Well-founded relation
・ Well-founded semantics
・ Well-known text
・ WELL-LD
・ Well-made play
・ Well-Manicured Man
・ Well-mannered
・ Well-order
・ Well-ordering principle
・ Well-ordering theorem
・ Well-pointed category
・ Well-posed problem
・ Well-quasi-ordering
・ Well-Schooled in Murder
・ Well-separated pair decomposition


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Well-founded relation : ウィキペディア英語版
Well-founded relation

In mathematics, a binary relation, ''R'', is well-founded (or wellfounded) on a class ''X'' if and only if every non-empty subset ''S⊆X'' has a minimal element; that is, some element ''m'' of any ''S'' is not related by ''sRm'' (for instance, "''m'' is not smaller than") for the rest of the ''s ∈ S''.
:\forall S \subseteq X\ (S \neq \varnothing \to \exists m \in S\;\; \forall s \in S\;\, ( s, m) \notin R)
(Some authors include an extra condition that ''R'' is set-like, i.e., that the elements less than any given element form a set.)
Equivalently, assuming some choice, a relation is well-founded if and only if it contains no countable infinite descending chains: that is, there is no infinite sequence ''x''0, ''x''1, ''x''2, ... of elements of ''X'' such that ''x''''n''+1 ''R'' ''x''n for every natural number ''n''.
In order theory, a partial order is called well-founded if the corresponding strict order is a well-founded relation. If the order is a total order then it is called a well-order.
In set theory, a set ''x'' is called a well-founded set if the set membership relation is well-founded on the transitive closure of ''x''. The axiom of regularity, which is one of the axioms of Zermelo–Fraenkel set theory, asserts that all sets are well-founded.
A relation ''R'' is converse well-founded, upwards well-founded or Noetherian on ''X'', if the converse relation ''R''−1 is well-founded on ''X''. In this case ''R'' is also said to satisfy the ascending chain condition. In the context of rewriting systems, a Noetherian relation is also called terminating.
==Induction and recursion==
An important reason that well-founded relations are interesting is because a version of transfinite induction can be used on them: if (''X'', ''R'') is a well-founded relation, ''P''(''x'') is some property of elements of ''X'', and we want to show that
:''P''(''x'') holds for all elements ''x'' of ''X'',
it suffices to show that:
: If ''x'' is an element of ''X'' and ''P''(''y'') is true for all ''y'' such that ''y R x'', then ''P''(''x'') must also be true.
That is,
:\forall x\in X\,(y\in X\,(y\,R\,x \to P(y))) \to P(x) )\to\forall x \in X\,P(x).
Well-founded induction is sometimes called Noetherian induction,〔Bourbaki, N. (1972) ''Elements of mathematics. Commutative algebra'', Addison-Wesley.〕 after Emmy Noether.
On par with induction, well-founded relations also support construction of objects by transfinite recursion. Let (''X'', ''R'') be a set-like well-founded relation and ''F'' a function that assigns an object ''F''(''x'', ''g'') to each pair of an element ''x ∈ X'' and a function ''g'' on the initial segment of ''X''. Then there is a unique function ''G'' such that for every ''x ∈ X'',
:G(x)=F(x,G\vert_{\{y: y\,R\,x\}})
That is, if we want to construct a function ''G'' on ''X'', we may define ''G''(''x'') using the values of ''G''(''y'') for ''y R x''.
As an example, consider the well-founded relation (N, ''S''), where N is the set of all natural numbers, and ''S'' is the graph of the successor function ''x'' → ''x'' + 1. Then induction on ''S'' is the usual mathematical induction, and recursion on ''S'' gives primitive recursion. If we consider the order relation (N, <), we obtain complete induction, and course-of-values recursion. The statement that (N, <) is well-founded is also known as the well-ordering principle.
There are other interesting special cases of well-founded induction.
When the well-founded relation is the usual ordering on the class of all ordinal numbers, the technique is called transfinite induction. When the well-founded set is a set of recursively-defined data structures, the technique is called structural induction. When the well-founded relation is set membership on the universal class, the technique is known as ∈-induction. See those articles for more details.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Well-founded relation」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.